package algorithm.graph;
import java.util.LinkedList;

/**
 *
 * @author DengZhiYuan
 * @version 1.0
 * @date 2022/12/24 18:07
 */
public class Graph {
    //有向有权图的邻接表表示
    private LinkedList<Edge> adj[];
    //顶点个数
    private int v;

    public Graph(int v) {
        this.v = v;
        this.adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            this.adj[i] = new LinkedList<>();
        }
    }

    public static void main(String[] args) {

    }
    public void test1(){
        Graph graph = new Graph(9);
        graph.addEdge(0,new Edge(0, 1, 4));
        graph.addEdge(0,new Edge(0, 7, 8));
        graph.addEdge(1,new Edge(1, 2, 8));
        graph.addEdge(1,new Edge(1, 7, 11));
        graph.addEdge(2,new Edge(2, 3, 7));
        graph.addEdge(2,new Edge(2, 5, 4));
        graph.addEdge(2,new Edge(2, 8, 2));
        graph.addEdge(3,new Edge(3, 4, 9));
        graph.addEdge(3,new Edge(3, 5, 14));
        graph.addEdge(7,new Edge(7, 1, 11));
        graph.addEdge(7,new Edge(7, 8, 7));
        graph.addEdge(7,new Edge(7, 6, 1));
        graph.addEdge(6,new Edge(6, 8, 6));
        graph.addEdge(6,new Edge(6, 5, 2));
        graph.addEdge(8,new Edge(8, 2, 2));
        graph.addEdge(8,new Edge(8, 6, 6));
        graph.addEdge(5,new Edge(5, 2, 4));
        graph.addEdge(5,new Edge(5, 3, 14));
        graph.addEdge(5,new Edge(5, 4, 10));

//        graph.addEdge(1,new Edge(0, 1, 4));
//        graph.addEdge(2,new Edge(1, 2, 8));
//        graph.addEdge(2,new Edge(8, 2, 2));
//        graph.addEdge(3,new Edge(2, 3, 7));
//        graph.addEdge(3,new Edge(5, 3, 14));
//        graph.addEdge(4,new Edge(3, 4, 9));
//        graph.addEdge(4,new Edge(5, 4, 10));
//        graph.addEdge(5,new Edge(3, 5, 14));
//        graph.addEdge(5,new Edge(2, 5, 4));
//        graph.addEdge(5,new Edge(6, 5, 2));
//        graph.addEdge(6,new Edge(7, 6, 1));
//        graph.addEdge(6,new Edge(8, 6, 6));
//        graph.addEdge(7,new Edge(0, 7, 8));
//        graph.addEdge(7,new Edge(1, 7, 11));
//        graph.addEdge(8,new Edge(2, 8, 2));
//        graph.addEdge(8,new Edge(7, 8, 7));
//        graph.addEdge(8,new Edge(6, 8, 6));
        graph.dijkstra(0,4,8);
    }


    /**
     * 给某一个顶点添加边
     * @param idx
     * @param edge
     */
    private boolean addEdge(int idx,Edge edge){
        if(v > idx){
            return  adj[idx].add(edge);
        }
        return false;
    }

    /**
     * 边的信息
     */
    private class Edge{
        //边的起点
        public int sid;
        //边的终点
        public int tid;
        //权重
        public int w;
        public Edge(int sid, int tid, int w) {
            this.sid = sid;
            this.tid = tid;
            this.w = w;
        }
    }


    /**
     * 贪心算法   迪克斯.特拉
     * 从顶点s到顶点t的最短路径
     * @author DengZhiYuan
     * @version 1.0
     * @date 2022/12/24 22:53
     * @param s
     * @param t
     * @return
     */
    public void dijkstra(int s, int t, int totalTop){
        //用来还原最短路径
        int[] predecessor = new int[totalTop];
        //从起始顶点到这个点的距离 保存
        Vertex[] vertices = new Vertex[totalTop];
        for (int i = 0; i < vertices.length; i++) {
            vertices[i] = new Vertex(i, Integer.MAX_VALUE);
        }
        PriorityQueue priorityQueue= new PriorityQueue(totalTop);
        //是否进入过队列
        boolean[] inQueue = new boolean[totalTop];
        //顶点到顶点的距离为0
        vertices[s].dist = 0;
        priorityQueue.add(vertices[s]);
        inQueue[s] = true;
        while (!priorityQueue.isEmpty()){
            Vertex minVertex = priorityQueue.poll();
            //最短路径产生了
            if(minVertex.id == t) break;
            for (int i = 0; i < adj[minVertex.id].size(); i++) {
                //取出一条minVertex相连的边
                Edge e = adj[minVertex.id].get(i);
                //minVertex ->nextVertex
                Vertex nextVertex = vertices[e.tid];
                //更新next的dist
                if(minVertex.dist + e.w < nextVertex.dist){
                    nextVertex.dist = minVertex.dist + e.w;
                    predecessor[nextVertex.id] = minVertex.id;
                    if(inQueue[nextVertex.id] == true){
                        priorityQueue.update(nextVertex);
                    }else{
                        priorityQueue.add(nextVertex);
                        inQueue[nextVertex.id] = true;
                    }
                }

            }
        }
        //输出最短路径
        System.out.println(s);
        print(s, t, predecessor);
    }


    /**
     * 打印
     * @author DengZhiYuan
     * @version 1.0
     * @date 2022/12/24 22:45
     * @param s
     * @param t
     * @param predecessor
     * @return
     */
    private void print(int s,int t,int[] predecessor){
        if(s == t) return;
        print(s,predecessor[t],predecessor);
        System.out.println("->"+t);
    }


}
